import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by L.jp
 * Description:给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
 * 输入：
 * {1,2,3,#,#,4,5}
 * 返回值：
 * [[1],[3,2],[4,5]]
 *
 * 说明：
 * 如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。
 * User: 86189
 * Date: 2022-01-16
 * Time: 17:08
 */

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
//思路：
//      1.首先想到不能用一个栈解决问题，那么可以再借助一个队列来临时存储每一层的所有节点
//      2.怎么达到之字形打印的，那么就需要借助一个存储指向的值flag，1代表l->r,2代表r->l,这样根据不同的指向将节点的左右孩子入队
//      3.这样一层就遍历完了，然后就将临时表的结果加入结果集，然后清空临时列表，将队列里的节点一次入栈
//      4.根据当前指向修改下一层的指向
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        //存放最终结果
        ArrayList<ArrayList<Integer>> ret=new ArrayList<>();
        if(pRoot==null){
            return ret;
        }
        //对于这个题目只借助一个栈是不行的，因为涉及到两个节点时，每次只能出一个节点，这样的话第一个节点的左右孩子节点就会先在另一个节点之前，乱了顺序
        Stack<TreeNode> stack = new Stack<>();
        //需要借助队列来临时存放每一层遍历到的节点，顺序存放入队，顺序入栈，倒序出栈
        Queue<TreeNode> queue = new LinkedList<>();
        //临时存储每一层的节点值
        ArrayList<Integer> tmp = new ArrayList<>();
        //先让头结点入栈
        stack.push(pRoot);
        int flag=1;//1表示从左到右访问节点，2表示从右到左访问节点
        //保持栈内一直有节点，知道为空时，说明整棵二叉树遍历完毕
        while(!stack.isEmpty()){
            //求得栈的长度，也就是每一层的节点个数
            int size=stack.size();
            //遍历完size个元素，说明一层完了，可以将整个遍历的结果加入到最终的列表，也需要修改指向
            for(int i=0;i<size;i++){
                //获取弹出的节点，以便根据指向让它的左右孩子入队列和入栈
                TreeNode cur = stack.pop();
                tmp.add(cur.val);//加入到临时的列表
                //通过指向改变先后访问的节点
                //为什么要借助两个额外的节点，因为每一层的指向不一样，入栈和入队的顺序也不一样，所以我们需要固定入的是start和end
                //但是每一次的start和end是不一样的，如果不借助这两个额外的节点的，只是让cur.left和cur.right入队的话，那么这样就真的固定了，但他是会变的
                TreeNode start=(flag==1) ? cur.left:cur.right;
                TreeNode end=(flag==1) ? cur.right:cur.left;
                //先后节点入队
                if(start!=null) queue.offer(start);
                if(end!=null) queue.offer(end);
            }
            //一层遍历完成，每一次都是新的临时列表入结果集
            ret.add(new ArrayList<>(tmp));
            //清空临时列表
            tmp.clear();
            //将队列里的所有节点入栈
            while(!queue.isEmpty()){
                stack.push(queue.poll());
            }
            //开始下一层的遍历，修改指向
            flag=(flag==1) ? 2 : 1;
        }
        return ret;
    }
}
